package Estrutura;

import java.util.LinkedList;
import java.util.Queue;

public class FordFulkerson

{

	private int[] parente;
	private Queue<Integer> fila;
	private int numerodeVertices;
	private boolean[] listadevisitas;
	public FordFulkerson(int numberOfVertices)	{

		this.numerodeVertices = numberOfVertices;
		this.fila = new LinkedList<Integer>();
		parente = new int[numberOfVertices + 1];
		listadevisitas = new boolean[numberOfVertices + 1];

	}

	public boolean buscaemprofundidade(int inicio, int fim, int matriz[][]) {

		boolean caminhoAchado = false;
		int destino, elemento;
		for (int vertice = 1; vertice <= numerodeVertices; vertice++)		{

			parente[vertice] = -1;
			listadevisitas[vertice] = false;

		}

		fila.add(inicio);
		parente[inicio] = -1;
		listadevisitas[inicio] = true;

		while (!fila.isEmpty()){

			elemento = fila.remove();
			destino = 1;

			while (destino <= numerodeVertices)		{

				if (matriz[elemento][destino] > 0 && !listadevisitas[destino])	{

					parente[destino] = elemento;
					fila.add(destino);
					listadevisitas[destino] = true;
				}

				destino++;
			}
		}

		if (listadevisitas[fim])	{

			caminhoAchado = true;
		}

		return caminhoAchado;
	}

	public int fordFulkerson(Grafo grafo, int origem, int destino)	{
		
		Integer[][] matriz = grafo.getMat();

		for(int k=0;k<grafo.obterNumVertices();k++){
			//Seta os valores de inalcancavel
			for(int j=0;j<grafo.obterNumVertices();j++){
				if(matriz[k][j]==null) {
					matriz[k][j] = 0;
				}
			}
		}
		
		int u, v;
		int fluxoMaximo = 0;
		int fluxodoCaminho;
		int[][] matrizResidual = new int[numerodeVertices + 1][numerodeVertices + 1];
		for (int verticedeOrigem = 1; verticedeOrigem <= numerodeVertices; verticedeOrigem++)	{

			for (int verticedoDestino = 1; verticedoDestino <= numerodeVertices; verticedoDestino++)	{

				matrizResidual[verticedeOrigem][verticedoDestino] = matriz[verticedeOrigem-1][verticedoDestino-1];
			}
		}

		while (buscaemprofundidade(origem, destino, matrizResidual))	{

			fluxodoCaminho = Integer.MAX_VALUE;
			for (v = destino; v != origem; v = parente[v])	{

				u = parente[v];
				fluxodoCaminho = Math.min(fluxodoCaminho, matrizResidual[u][v]);

			}

			for (v = destino; v != origem; v = parente[v])	{

				u = parente[v];
				matrizResidual[u][v] -= fluxodoCaminho;
				matrizResidual[v][u] += fluxodoCaminho;
			}

			fluxoMaximo += fluxodoCaminho;
		}

		return fluxoMaximo;
	}

}
